package com.lx.algorithm.monotoneStack;

import java.util.Stack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-07 15:36:50
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-07     张李鑫                     1.0         1.0 Version
 */
// 测试链接：https://leetcode.com/problems/largest-rectangle-in-histogram
public class LargestRectangleInHistogram {
    /**
     * 给定一个非负数组arr，代表直方图
     * 返回直方图的最大长方形面积
     * <p>
     * 优化:使用数组代替栈
     */

    public static int largestRectangleArea(int[] heights) {
        int[] arr = new int[heights.length];
        MyStack stack = new MyStack(arr);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                Integer pop = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek();
                max = Math.max(max, (i - 1 - left) * heights[pop]);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            int left = stack.isEmpty() ? -1 : stack.peek();
            max = Math.max(max, (heights.length - 1 - left) * heights[pop]);
        }
        return max;
    }

    //实现一个简易的栈 提高性能
    public static class MyStack {
        int[] arr;
        int start;

        public MyStack(int[] arr) {
            this.arr = arr;
            start = -1;
        }

        public int peek() {
            return arr[start];
        }

        public boolean isEmpty() {
            return start == -1;
        }

        public int pop() {
            return arr[start--];
        }

        public void push(int val) {
            arr[++start] = val;
        }
    }
}
